Divisibilidad en semigrupos y anillos (página 2)

Partes: 1, 2

de estos

(3.8) (3.9) '' ' 18 mismos elementos, d será un divisor de
d ' . Ahora, según el teorema 3.1, resulta que d y
d’ están asociados. La demostración del
teorema siguiente es análoga con la del teorema anterior.
Teorema 3.11: Si los elementos a y b están asociados con
los elementos a ' y b ' , respectivamente, y m ?m '? es un
mínimo común múltiplo de a y b (de a ' y b '
), entonces m y m ' están asociados. El máximo
común divisor y el mínimo común
múltiplo de n elementos del semigrupo G se define de la
misma manera que en el caso de dos elementos. Definición
3.9: Si a1 , a2 , ? an ? G , d ? G es un máximo
común divisor de a1 , a2 , ? an si d es un divisor
común de estos elementos y cualquier otro divisor
común de ellos es un divisor de d . Definición
3.10: Si a1 , a2 , ? an ? G , m ? G es un mínimo
común múltiplo de a1 , a2 , ? an si m es un
múltiplo común de estos elementos y cualquier otro
múltiplo común es un múltiplo de m .
Obviamente, como en el caso de dos elementos, el máximo
común divisor y el mínimo común
múltiplo de n elementos son determinados hasta un factor
invertible. Así, (a1 , a2 , ? an ) y [ a1 , a2 , ? an ] ,
designarán un máximo común divisor y un
mínimo común múltiplo cualquiera de los
elementos a1 , a2 , ? an respectivamente. Teorema 3.12: Si n ? N
? ?0,1? y dos elementos cualesquiera del semigrupo G tienen
máximo común divisor, entonces (a1 , a2 , ? an ) y
[ a1 , a2 , ? an ] , existen cualesquiera que sean a1 , a2 , ? an
? G . Demostración: Primero, si dos elementos cualesquiera
de G tienen máximo común divisor, entonces,
según el teorema 3.9, tienen también mínimo
común múltiplo. Si 2 ? k ? n ? 1 , sean d k y mk
definidos por recurrencia de la manera siguiente: d 2 ? ?a1 , a2
? ; d k ?1 ? ?d k , ak ?1 ? m2 ? ?a1 , a2 ? ; mk ?1 ? ?mk , ak ?1
? De (3.8) resulta que a1 Dd 2 , di Dd n y ai Ddi , donde i ? ?2
, n ?. Por tanto d i Dd n , cualquiera que sea i ? ?1, n ? . Si d
n' es un divisor común cualquiera de a1 , a2 , ? an ,
entonces se puede demostrar por recurrencia: di Dd n ?2 ? i ? n
?1? y an Dd n ? dn Dd n , y por tanto d n es un máximo
común divisor de a1 , a2 , ? an . De manera análoga
resulta que mn es un mínimo común múltiplo
de a1 , a2 , ? an . Si sabemos calcular el máximo
común divisor y el mínimo común
múltiplo de dos elementos, entonces (3.8) y (3.9) permiten
calcular el máximo común divisor y el mínimo
común múltiplo de n elementos y este proceso es
fácilmente programable. Evidentemente, una
permutación de los elementos a1 , a2 , ? an entre si
cambiaría los resultados solo en un factor invertible.
Definición 3.11: a ? G es un elemento irreducible si no es
invertible y no tiene otros divisores que los elementos
invertibles o los elementos asociados con a . Definición
3.12: p ? G es un elemento primo si no es invertible y a .b D p ?
aDp ó bDp . Teorema 3.13: Cualquier elemento primo es
irreducible. En efecto, si p ? a .b , entonces de pDp resulta que
a.b D p y así tendremos a D p ó b D p , lo que
implica que o bien a o bien b está asociado con p . Si a
?b? está asociado con p entonces b ?a ? es un elemento
invertible. La recíproca de este teorema no es verdadera.
Teorema 3.14: Si a es un elemento irreducible del semigrupo G y a
no es un divisor de b , entonces a y b son primos entre
sí. Demostración: Al no ser a un divisor de b ,
ningún elemento asociado con a puede ser un divisor de b
.

19 Sea ahora d un divisor común de a y b . Al ser d un
divisor del elemento irreducible a , d es o bien un elemento
invertible o bien es un elemento asociado con a . Pero, teniendo
en cuenta que d es también un divisor de b , d no puede
estar asociado con a , ya que a no es un divisor de b . Entonces,
cualquier divisor común d de a y b es un elemento
invertible. Por consiguiente, a y b son primos entre sí.
Teorema 3.15: Si dos elementos cualesquiera del semigrupo G
tienen máximo común divisor, entonces cualquier
elemento irreducible es un elemento primo. Demostración:
Si c es un elemento irreducible y a.b D c , entonces,
según el teorema 3.13, de la falsedad de aDc
resultaría que el elemento neutro e es un máximo
común divisor de los elementos c y a . Según el
teorema 3.8, b ? b . e es un máximo común divisor
de c . b y a.b y, dado que c es un divisor común de c . b
y a . b , resulta que c es un divisor de b . Teorema 3.16: Dos
elementos a y b irreducibles y no asociados son primos entre
sí. Demostración: El elemento a no es un divisor de
b puesto que al ser b un elemento irreducible, b ? a . q
sería posible solo para q invertible y en este caso a y b
estarían asociados. De esta manera, el teorema 3.16 es
consecuencia del teorema 3.14. Teorema 3.17: Dos elemento primos
no asociados a y b son primos entre si. Demostración: Si a
y b son dos elementos primos entre sí pero no están
asociados, entonces, según el teorema 3.13, los elementos
a y b son irreducibles y no asociados. Así, el teorema
3.17 es consecuencia del teorema 3.16. Teorema 3.18: Si el
elemento a está asociado con un elemento irreducible b
entonces a es irreducible. Demostración: En efecto, b ?
a.u , donde u es un elemento invertible. Suponiendo que b no es
irreducible se podría escribir que b ? q . r , donde q y r
no son invertibles y por tanto, tampoco están asociados
con b . Así resultaría que a ? b .u ?1 ? q . r .u
?1 El elemento r .u ?1 no puede ser invertible puesto que en este
caso r sería también invertible. De esta manera, q
es un divisor no es invertible de a y tampoco está
asociado con a , es decir, a no es irreducible. La
contradicción obtenida demuestra que b debe ser
irreducible. Teorema 3.19: Un elemento asociado con un elemento
primo es primo. Demostración: Si p es un elemento primo y
p ' ? p .u , donde u es un elemento invertible, supongamos que a
.b D p ' . Entonces, a .b ? p .u . q Dado que p es un elemento
primo, resulta que aDp ó bDp , es decir aDp ' ó bDp
' . §. 4. Divisibilidad en el conjunto de los números
naturales. Sea N el conjunto de los números naturales. Con
respecto la multiplicación, N ? ?0? es un semigrupo
conmutativo con el elemento neutro 1, donde se cumple la regla de
simplificación. Así, en el semigrupo ?N ? ?0? , .?
quedarán válidas todas las consideraciones del
párrafo anterior. El número 1 siendo el
único elemento invertible del semigrupo ?N ? ?0? , .?, dos
elementos de este semigrupo no pueden tener más de un
máximo común divisor o más de un
mínimo común múltiplo. La estructura
algebraica de N es mucho más compleja que la de un
semigrupo. En N se definen tres leyes de composición
internas: la adición, la multiplicación y una
sustracción no siempre posible. ?N , .? es un semigrupo
multiplicativo con el elemento neutro 1 y ?N , ? ? es un
semigrupo aditivo con el elemento neutro 0. La
multiplicación es distributiva respecto la adición
y la sustracción. Finalmente, existe en N una
relación de orden respecto al cual N queda totalmente y
bien ordenado. Esto quiere decir que dos elementos cualesquiera
de N son comparables y que cualquier subconjunto no vacío
de N tiene un elemento más pequeño. Estas
circunstancias permiten demostrar gran cantidad de teoremas sobre
la divisibilidad en N que no se podrían formular o
demostrar con los medios disponibles en el semigrupo ?N , .? .
Teorema 4.1: Si d ? N es un divisor común de a, b ? N ,
entonces d es un divisor de a ? b . En efecto, de

20 a ? d .a1 y b ? d .b1 , resulta que a ? b ? d . a1 ? d .b1 ? d
. ?a1 ? b1 ? Teorema 4.2: Si d ? N es un divisor de a ? N ,
entonces d es un divisor de a.b , cualquiera que sea b ? N . En
efecto, puesto que a ? d .a1 , a .b ? ?d . a1 ?.b ? d . ?a1 .b ?
Teorema 4.3: Si a, b, c ? N , a ? b ? c y d ? N es un divisor de
a y b , entonces d es un divisor de c . En efecto, de a ? d .a1 ,
b ? d .b1 y a ? b ? c resulta que d . a1 ? d .b1 ? c , y puesto
que a ? b ? a1 ? b1 , tendremos c ? d . ?a1 ? b1 ? Teorema 4.4:
Si a, b ? N y b ? 0 , entonces existen q, r ? N tales que a ? b .
q ? r y 0 ? r ? b Demostración: Si a ? b , entonces Si a ?
b , entonces Si a ? b , sea a ? b . 0 ? a , donde a ? b a ? b .1
? 0 , donde 0 ? b M ? ?n / n ? N , a ? b . n ? ? N . Puesto que b
? 0 , b ? 1 ? ? , donde ? ? 0 . Entonces b . ?a ? 1? ? a ? ? . ?a
? 1? ? a , y así ?a ? 1? ? M . Por tanto, M no es el
conjunto vacío. Puesto que cualquier subconjunto no
vacío de N posee un elemento más pequeño,
sea n0 el elemento más pequeño de M. Dado que a ? b
y n0 ? 0 , resulta que n0 ? 1 . Si se pone q0 ? n0 ? 1 , entonces
q0 ? M y, por consiguiente a ? b .q0 , es decir a ? b . q0 ? 0 .
La desigualdad a ? b . q0 ? b es imposible puesto que esto
implicaría a ? b .n0 . Así pues a ? b . q0 ? r ,
donde 0 ? r ? b . Observación 4.1: Si a ? N , el
máximo común divisor de a y 0 es a , puesto que a
es un divisor común de a y 0, y cualquier divisor
común de a y 0 es un divisor de a . Observación
5.2: Si a ? N , el mínimo común múltiplo de
a y 0 es 0 puesto que 0 es un múltiplo común de a y
0, y cualquier múltiplo de a y 0 es cero (por tanto un
divisor de 0). Teorema 4.5: Dos elementos cualesquiera de ?N , .?
tienen máximo común divisor. Demostración:
Teniendo en cuenta la observación (4.1), es suficiente
demostrar el teorema para a, b ? N ? ?0?. Según el teorema
5.4, existirán q1 , r1 ? N tales que a ? b . q1 ? r1 y r1
? b . Si r1 ? 0 , existirán q2 , r2 ? N tales que b ? r1 .
q2 ? r2 y r2 ? r1 . Si r2 ? 0 , existirán q3 , r3 ? N
tales que r1 ? r2 . q3 ? r3 y r3 ? r2 . Si r3 ? 0 , se
continúa el proceso anterior. No obstante, este proceso no
puede continuarse indefinidamente puesto que en el caso contrario
se llegaría a una sucesión de números
naturales estrictamente decreciente e infinita: b, r1 , r2 , r3 ,
? , lo que es imposible, al existir solo un número finito
de números naturales menores que b . Suponiendo que rn?1
es el primer resto nulo, tendremos: a ? b . q1 ? r1 b ? r1 . q2 ?
r2

21 r1 ? r2 . q3 ? r3 …………… rn?2 ? rn?1 . qn ? rn rn?1 ?
rn . qn?1 . (4.1) Entonces rn es divisor de rn ?1 y, según
el teorema 4.1, rn será también divisor de rn?1 . q
. Al ser rn divisor común de rn y rn?1 . qn , según
el teorema 4.1, rn será divisor también de rn ? 2 .
A continuación, al ser rn divisor común de rn ?1 y
rn ? 2 , resultará que rn es divisor de rn?3 y, repitiendo
éste razonamiento un número finito de veces, se
llega a la conclusión de que rn es divisor común de
a y b . Al revés, si d ? N es divisor común de a y
b , entonces, según los teoremas 4.2 y 4.3, d será
divisor de r1 . Al ser d divisor común de b y r1 , el
mismo razonamiento conduce a la conclusión de que d es un
divisor de r2 . Repitiendo este razonamiento de un número
finito de veces, resultará que d es divisor de rn . De
esta manera, rn es divisor común de a y b , y cualquier
divisor común de a y b es un divisor de rn , por tanto, rn
es el máximo común divisor de a y b . Al demostrar
el teorema 4.5, no solo se ha demostrado la existencia del
máximo común divisor en ?N , .? sino se ha
encontrado también el método práctico para
su cálculo. Este método se expresa por las
fórmulas 4.1 y se llama el algoritmo de Euclides. Teorema
4.6: Dos elementos cualesquiera de ?N , .? tienen mínimo
común múltiplo. Demostración: Teniendo en
cuenta la observación 4.2, es suficiente demostrar el
teorema para a, b ? N . Según el teorema 4.5, dos
elementos cualesquiera de N ? ?0? tienen máximo
común divisor y entonces el teorema 2.9 garantiza la
existencia del mínimo común múltiplo de dos
elementos cualesquiera de N ? ?0?. Observación 4.3: Al ser
1 el único elemento invertible en el semigrupo ?N , .? ,
el máximo común divisor y el mínimo
común múltiplo de dos elementos de N son
únicos, y de 2.9 resulta que ?a , b?.?a , b? ? a .b , ,
cualesquiera que sean a, b ? N . Cuando los números x e y
no son demasiado grandes, dentro de un programa Visual-Basic, el
máximo común divisor d podría hallarse
efectuando la instrucción d ? mcd ?x, y ? , donde la
función mcd se ha definido de la manera siguiente: Public
Function mcd(ByVal a As Double, ByVal b As Double) As Double Dim
a1 As Double, b1 As Double, c1 As Double Dim q As Double, r As
Double a1 = a: b1 = b If a1 < b1 Then c1 = a1: a1 = b1: b1 =
c1 End If r=1 Do Until r = 0 q = a1 / b1: r = a1 – b1 * Int(q) If
r <> 0 Then a1 = b1: b1 = r End If Loop mcd = b1 End
Function Naturalmente, el programa tiene que asegurar que los
números x e y son enteros. En Visual-Basic existe la
instrucción a ? b mod c . Esto quiere decir que el resto
de la división de a entre c es b . Utilizando esta
instrucción, la función mcd se podría
construir también de la manera siguiente: Public Function
mcd(ByVal a As Double, ByVal b As Double) As Double Dim a1 As
Double, b1 As Double, c1 As Double, r as Double

22 a1 = a: b1 = b If a1 < b1 Then c1 = a1: a1 = b1: b1 = c1
End If r=1 Do Until r = 0 r=a1 mod b1 If r <> 0 Then a1 =
b1: b1 = r Loop mcd = b1 End Function Para calcular el
mínimo común múltiplo m de dos
números naturales x e y, según la
observación 4.3, se podría proceder de la manera
siguiente: d ? mcd ?x, y ? y m ? ?x / d ? ? y . La
codificación de este cálculo es la siguiente:
Public Function mcm(ByVal a As Double, ByVal b As Double) As
Double Dim d As Double, m As Double, a1 as double d =
mcd(a,b):a1=a/d:m=a1*b mcm = m End Function Si se trata calcular
el máximo común divisor o el mínimo
común múltiplo de números naturales grandes
se pueden utilizar las funciones MaxComDiv y MinComMult ,
expuestas en la monografía: Operaciones con números
enteros largos. Sin embargo, aquí se exponen
también las versiones más sencillas siguientes:
Public Function mcdNg(ByVal a As String, ByVal b As String) As
String Dim a1 As String, b1 As String, c1 As String Dim q As
String, r As String, n As Integer Dim rr() As String, x(2) As
String, dif As String a1 = a: b1 = b: n = 14 x(1) = a1: x(2) =
b1: dif = Restar(x(), n) If Left$(dif, 1) = "-" Then c1 = a1: a1
= b1: b1 = c1 End If r = "1" Do Until r = "0" Or r = "-0" x(1) =
a1: x(2) = b1: rr() = DivisionEuclidea(x(), n) q = rr(1): r =
rr(2) If r <> "0" Then a1 = b1: b1 = r End If Loop mcdNg =
b1 End Function Public Function mcmNg(ByVal a As String, ByVal b
As String) As String Dim n As Integer, x(2) As String, d As
String Dim rr() As String, pr As String n = 7: x(1) = a: x(2) =
b: d = mcdNg(a, b) x(1) = a: x(2) = b: pr = Multiplicar(x(), n)
x(1) = pr: x(2) = d rr() = DivisionEuclidea(x(), 30) mcmNg =
rr(1) End Function Puesto que dos números naturales
siempre tienen máximo común divisor, según
los teoremas 4.13 y 4.15, los números primos coinciden con
los números irreducibles. Así, para averiguar que
un número natural n es primo, hay que demostrar que este
número no tiene otros divisores que 1 y n . Esto se
podría hacer dividiendo el número n sucesivamente
con los números naturales situados entre 2 y n ? 1 , ambos
inclusive. Si al efectuar estas divisiones, en cierto momento la
división es exacta, el número no es primo. En el
caso contrario, el número será primo. El teorema
siguiente reducirá considerablemente el número de
las divisiones necesarias, para poder decidir si un número
es primo o no.